package utils.node;

/**
 * 定义一个双头链表队列，可以从头部插入，头部移除，尾部插入，尾部移除
 *
 * @param <T>
 */
public class DoubleEndsQueue<T> {
    //用双向链表 定义 头部，和尾部指针
    public DoubleNode<T> head;
    public DoubleNode<T> tail;

    /**
     * 从头部向队列中添加值
     *
     * @param value
     */
    public void addFromHead(T value) {
        // 创建一个节点存储传进来的value
        DoubleNode cur = new DoubleNode(value);
        // 如果当前队列为空（没有节点）,则头，尾都指向这个新节点cur
        if (null == head) {
            head = cur;
            tail = cur;
        } else {//节点不为空，往头部添加，head前移，尾部不动
            cur.nextNode = head;
            head.lastNode = cur;
            head = cur;
        }
    }

    /**
     * 从尾部向队列中添加值
     *
     * @param value
     */
    public void addFromBottom(T value) {
        DoubleNode<T> cur = new DoubleNode(value);
        if (null == head) {
            head = cur;
            tail = cur;
        } else {
            cur.lastNode = tail;
            tail.nextNode = cur;
            tail = cur;
        }
    }

    /**
     * 从头部取值
     *
     * @return
     */
    public T popFromHead() {
        if (null == head) {
            return null;
        }
        DoubleNode<T> cur = head;
        // 头部和尾部指向同一个节点==>只有一个节点
        if (head == tail) {
            head = null;
            tail = null;
        } else { // 有两个及以上节点
            head = head.nextNode;
            head.lastNode = null;
            cur.nextNode = null;
        }
        return cur.value;
    }

    /**
     * 返回顶部元素的值
     * @return
     */
    public T getTheHead(){
        if (null == head){
            return null;
        }
        return head.value;
    }
    /**
     * 从尾部取值
     *
     * @return
     */
    public T popFromBottom() {
        if (null == head) {
            return null;
        }
        DoubleNode<T> cur = tail;
        // 只有一个元素
        if (head == tail) {
            head = null;
            tail = null;
        } else { // 有两个及以上元素
            tail = tail.lastNode;
            tail.nextNode = null;
            cur.lastNode = null;
        }
        // 返回底部元素；
        return cur.value;
    }

    /**
     * 返回最底部元素的值
     * @return
     */
    public Object getTheBottom(){
        if (null==head){
            return null;
        }
        return tail.value;
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return head == null;
    }
}
